package phaseI;
import java.util.ArrayList;

public class NFAScanner {
	private NFATable table;
	private ArrayList<String> states;

	public NFAScanner(NFATable table) {
		this.table = table;
	}
	
	public boolean matches(String arg) {
		states = new ArrayList<String>();
		states.add("1");
		int trans = 0, clones = 0;
		
		for (int i = 0; i < arg.length(); i++) {
			ArrayList<String> nextStates, arr;
			nextStates = new ArrayList<String>();
			for (String state:states) {
				arr = table.getStatesFromTransition(state, "epsilon");
				if (arr != null) nextStates.addAll(arr);
			}
			if (!nextStates.isEmpty()) {
				states.addAll(nextStates);
				clones += nextStates.size();
				trans += nextStates.size();
			}
			nextStates.clear();
			for (String state:states) {
				arr = table.getStatesFromTransition(state, arg.substring(i, i+1));
				if (arr != null) {
					nextStates.addAll(arr);
					clones += nextStates.size() - 1;
					trans += nextStates.size();
					//System.out.println(nextStates);
				}
			}
			if (nextStates.isEmpty()) {
				//System.out.printf("Transitions: %d\nClones: %d\n", trans, clones);
				return false;
			}
			states = nextStates;
		}
		//System.out.printf("Transitions: %d\nClones: %d\n", trans, clones);
		return acceptingState();
	}
	
	private boolean acceptingState() {
		for (String s:states) {
			if (table.hasEndState(s)) return true;
		}
		return false;
	}
}
